//
// Created by Poyyo on 2021/6/16.
//

#include "Graph/GraphInMatrixImpl.h"
#include <stack>

using namespace std;

/**
 * 利用深度遍历算法求解有向图的联通分量问题
 * @param graph 有向图
 * @param stack
 * @param id
 * @param findId
 * @return
 */
bool dfs_fun(GraphInMatrixImpl &graph, stack<int> &stack, int id, int findId) {
    // 将id压栈
    stack.push(id);
    // 标记id已经入栈
    graph.Select(id);
    // 当栈飞控
    while (!stack.empty()) {
        // 获取栈顶元素
        auto visitId = stack.top();
        if (visitId == findId) {
            return true;
        }
        // 获取与id有连接的所有结点
        auto nextVs = graph.GetLinkedVertexes(visitId);
        // 标记是否存在还没访问的与id相邻的结点
        auto flag = false;
        // 遍历id的邻接结点
        for (auto item : nextVs) {
            // 如果存在结点未访问，压栈并结束循环
            if (!graph.getVertexes()[item].isSelected()) {
                stack.push(item);
                // 标记item已经入栈
                graph.Select(item);
                flag = true;
                break;
            }
        }
        // 如果id邻接结点没有或者都被访问过，则访问id
        if (!flag) {
            stack.pop();
        }
    }
    return false;
}

bool find(GraphInMatrixImpl& graph, int index, int findId) {
    stack<int> stack;
    auto &vertexes = graph.getVertexes();
    return dfs_fun(graph, stack, index, findId);
}


/*
1 2 2 3
2 0
3 1 4
4 1 5
5 0
 */
int main() {
    GraphInMatrixImpl graphInMatrix;
    graphInMatrix.ToString();
    int index, findId;
    cin >> index >> findId;
    cout << find(graphInMatrix, index, findId);
}